

class Node{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    insert(node){
        if(node.value < this.value){
            // 左子树
            if(this.left){
                this.left.insert(node);
            }else{
                this.left = node;
                node.parent = this;
            }
        }else{
            // 插入到右子树
            if(this.right){
                this.right.insert(node);
            }else{
                this.right = node;
                node.parent = this;
            }
        }
    }


    ///// 前中后序遍历
    qianxu_walk(func){
        func(this.value);
        if(this.left){
            this.left.qianxu_walk(func);
        }
        if(this.right){
            this.right.qianxu_walk(func);
        }
    }

    zhong_walk(func){
        if(this.left){
            this.left.zhong_walk(func);
        }
        func(this.value);
        if(this.right){
            this.right.zhong_walk(func);
        }
    }

    hou_walk(func){
        if(this.left){
            this.left.hou_walk(func);
        }
        if(this.right){
            this.right.hou_walk(func);
        }
        func(this.value);
    }

    calBalanceFactor(){
        let leftHeight = this.calLeftHeight();
        let rightHeight = this.calRightHeight();
        return Math.abs(leftHeight - rightHeight);
    }

    isBalance(){
        let bf = this.calBalanceFactor();
        return bf <= 1;
    }

    isTreeBalance(){

       if(!this.isBalance()){
           return false;
       }

       let bLeft = true,bRight = true;
       if(this.left){
           bLeft = this.left.isTreeBalance();
       }
       if(this.right){
           bRight = this.right.isTreeBalance();
       }
        return bLeft && bRight;
    }

    calLeftHeight(){
        // 计算左子树高度
        if(!this.left){
            return 0;
        }
        return this.left.calHeight();
    }

    calRightHeight(){
        if(!this.right){
            return 0;
        }
        return this.right.calHeight();
    }

    calHeight(){
        // 计算节点高度
        if(!this.left && !this.right){
            return 0;
        }

        let leftHeight,rightHeight;
        if(this.left){
            leftHeight = this.left.calHeight();
        }else{
            leftHeight = 0;
        }

        if(this.right){
            rightHeight = this.right.calHeight();
        }else{
            rightHeight = 0;
        }

        return 1 + Math.max(leftHeight,rightHeight);
    }

    static createFromArray(arr){
        if(arr.length < 1){
            return null;
        }

        let len = arr.length;
        let root = new Node(arr[0]);
        let idx = 1;
        while (idx < len){
            let num = arr[idx];
            let node = new Node(num);
            root.insert(node);
            idx++;
        }
        return root;
    }

    static createAVLFromArray(arr){

    }
}


let arr = [10,4,7,2,8,12,11,1,15,22];
let tree = Node.createFromArray(arr);

// tree.qianxu_walk(console.log.bind(console));

// let log = console.log.bind(console);
// tree.hou_walk(log);


// console.log(tree.calHeight());
// console.log(tree.calLeftHeight());
// console.log(tree.calRightHeight());


console.log(tree.isTreeBalance());
